package findDisappearedNumbers;

import java.util.*;

public class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
//        int[] arr = new int[nums.length+1];
//        for (int i = 0; i < nums.length; i++) {
//            arr[nums[i]] = 1;
//        }
//        List<Integer> list = new ArrayList<>();
//        for (int i = 1; i <= arr.length; i++) {
//            if(arr[i]!=1){
//                list.add(i);
//            }
//        }
//        return list;

        // 原地修改
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            int index = Math.abs(nums[i])-1;
            nums[index] = -Math.abs(nums[index]);
        }
        for (int i = 0; i < nums.length; i++) {
            if(nums[i]>0){
                list.add(i);
            }
        }
        return list;
    }
}
